package com.xiaoyu.arrays;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @program: DS_and_A
 * @description: 两数之和, leetCode 第一题
 * @author: YuWenYi
 * @create: 2021-04-22 08:32
 **/


public class Two_Sum_1 {
    /*
    * 个人初级解法!  ---> LeetCode通过
    * 数组{2,11,7,15}  目标值9
    * 第一次循环: i=0,j=1,即全部加一遍,2+11,2+7,2+15,看看谁等于目标值
    * 同理第二次循环:i=1,j+2
    * */
 /*   public static int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                if (target == nums[i] + nums[j]){
                    return new int[]{i,j};
                }
            }
        }
        return null;
    }*/

    /*
    * 评论区高级解法,使用hashmap,通过补数来求值
    *
    * 1.创建hashmap
    * 2.循环数组
    *   判断key中是否有目标值的补数
    *       如果有,那么成功找到两个数字,按逻辑返回其下标即可
    *       如果没有,那么将target-nums[i](补数)作为key,索引值i作为value,保存在map中,继续循环
    * */
    public static int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (hashMap.containsKey(nums[i])){  //map中是否包含补数?  注意,这里使用了自动装箱
                //num1的索引为之前保存的value值,num2的索引为等于补数的值的索引:i
                return new int[]{hashMap.get(nums[i]),i};
            }
            //key为补数,value为索引,我们要知道,  target-num1 = 补数,因此只需要知道下一个数字是否为补数,就能找到第二个数!
            hashMap.put(target-nums[i],i); //{7,0},{-11,1},{-2,2} --找到7,然后i=map.get(7)-->0,j=3
        }
        return null;
    }

    public static void main(String[] args) {
        int[] nums = {5,5,11,8,15};
        int target = 10;
        int[] sum = twoSum(nums, target);
        System.out.println(Arrays.toString(sum));
    }
}
